极客时间 排序算法O(n^2) O(nlogn)

所谓的算法稳定性就是

冒泡排序

比如对于4，5，6，3，2，1

冒泡的过程可以优化，当某次操作没有数据交换时，说明已经到达完全有序。

一，冒泡排序的过程只涉及相邻数据的交换操作，只需要常量级的临时空间，所以空间复杂度为O(1)，是一个原地排序算法。
二，为保证冒泡排序算法的稳定性，当有相邻的两个元素大小相等的时候，不做交换。所以冒泡排序是稳定的。
三，最好情况，要排序的数据已经是有序的，只需进行一次冒泡操作即可结束，最好时间复杂度是O(n)。最坏要排序的数据是倒序的，需要进行n次冒泡，最坏为O(n^2)
在最坏情况下，进行n (n-1) / 2次交换，最好情况下不需要进行交换，取中间值为n (n-1) / 4来表示平均，所以平均复杂度为O(n^2)

插入排序

插入排序包括元素的比较与元素的移动两种操作。
一，插入排序不需要额外的存储空间，所以空间复杂度是O(1)，所以是一个原地排序算法。
二，对于值相同的元素，通过选择后面出现的元素，就可以保持原有的前后顺序不变，所以插入排序是稳定的排序算法。
三，最好情况是有序，即为从头到尾遍历一遍为O(n)。最坏为倒序，每次要插到第一个位置，并且需要大量的移动数据，最坏情况时间复杂度为O(n^2)。
在数组中插入一个数据的平均时间复杂度是O(n)，对于插入排序来说，每次插入操作都相当于在数组中插入一个数据，循环n次，所以平均时间复杂度为O(n^2)。

选择排序

选择排序算法的实现思路有点类似插入排序，但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。

选择排序空间复杂度为O(1)，是一种原地排序算法，最好最坏和平均时间复杂度都是O(n^2)。选择排序每次都要找到剩余未排序元素中的最小值，并和前面的元素交换位置，破坏了稳定性，所以选择排序是一种不稳定的排序算法。

归并排序

归并排序使用的就是分治思想。分治是一种解决问题的处理思想，递归是一种编程技巧。分治算法一般都是用递归来实现的。
归并排序的递推公式：

merge函数的具体操作。需要借助一个临时数组tmp

一，对于A[p…q]和A[q+1…r]之间值相同的元素，可以将A[p…q]中的元素放入tmp数组中，就保证了值相同的元素合并前后顺序不变，所以归并排序是个稳定的排序。
二，由图中可以看出过程不论是最好最坏还是平均情况，时间复杂度都是O(nlogn)
三，显而易见，归并排序不是原地排序，递归代码的空间复杂度并不能像时间复杂度那样累加，所以空间复杂度是O(n)。

快速排序

快排主要思想：如果要排序数组中下标为p到r之间的一组数据，选择p到r之间任意一个数据作为pivot(分区点)。遍历p到r之间的数据，将小于pivot的放到左边，将大于pivot的放到右边，将pivot放到中间，至此，p到r就被分为了三部分。

根据分治、递归的处理思想，可以用递归排序下标从p到q-1之间的数据和下标从q+1到r之间的数据，直到区间缩小为1，就说明所有的数据都有序了。

partition()分区函数就是随机选择一个元素作为pivot(一般情况下，可以选择p到r区间的最后一个元素)，然后对A[p…r]分区，函数返回pivot的下标。我们希望快排是个原地排序算法。

可以发现归并排序的处理是由下向上的，快排是由上到下的。

性能分析：快排是一种原地、不稳定的排序算法。由图中可见，有交换的过程，所以是不稳定的，一般来说快排的时间复杂度是O(nlogn)，最差情况是数组中的数据原来已经是有序的，选择最后一个元素作为pivot，分区就是极度不均衡的，那么复杂度就从O(nlogn)退化到O(n^2)，最佳情况就是分区极度均衡，为O(nlogn)，平均来看在大部分时间里，时间复杂度可以做到O(nlohn)，只有在极端情况下，会退化到O(n^2)，但是也有很多方法将这个概率降到很低。

问题:O(n)时间复杂度内求无序数组的第K大元素。

选择A[0…n-1]的最后一个元素A[n-1]作为pivot,对数组原地分区，这样数组就分为了三部分,A[0…p-1],A[p],A[p+1…n-1]。

如果p+1=K，那么A[p]就是要求解的元素；如果K>p+1,说明在右侧，然后同样思路在右边区间去找。

O(n)时间找到一组数据第K大元素

解题思路:利用快排中分区的思想,选择数组区间A[0…n-1]的左右一个元素A[n-1]作为pivot,对数组A[0…n-1]原地分区,这样数组就分成了三部分,A[0…p-1],A[p],A[p+1…n-1],如果p+1=k那么A[p]就是要求解的元素,如果K>p+1,则说明第K大的元素在A[p+1…n-1]这个区间,否则在A[0…p-1]这个区间,递归的查找第K大的元素。